Two-party general secure function evaluation (SFE) allows two parties to evaluate any function on their respective inputs x and y, while maintaining the privacy of both x and y. Efficient SFE algorithms enable a variety of electronic transactions, previously impossible due to mutual mistrust of participants. For example, SFE algorithms have been employed in auctions, contract signing and distributed database mining applications. The problem of secure computation has been solved for both semi-honest and malicious players. Generally, having access to a semi-honest server resolves the problem of malicious circuit generation. As computation and communication resources have increased, SFE has become truly practical for common use. A malicious SFE model provides a guarantee of complete privacy of the players' inputs. Existing generic two-party SFE algorithms typically employ Garbled Circuits (GCs). For a detailed discussion of GCs, see, for example, Y. Lindell and B. Pinkas, “A Proof of Yao's Protocol for Secure Two-Party Computation,” Journal of Cryptology, 22 (2):161-188 (2009).
Under a Garbled Circuit implementation, a Boolean circuit representing the computed function is encrypted by a first party and is given to a second party for evaluation. The evaluation proceeds under encryption, and hence the second party cannot deviate from the protocol. While such existing generic two-party SFE algorithms based on Garbled Circuits have significantly improved the privacy and security of two party transactions, a number of limitations remain, which, if overcome, could further improve the efficiency, utility and/or security of generic two-party SFE algorithms. For example, in the case of multiple SFE executions between the same parties, there is a need for verifying input consistency between executions. The second party, however, can perform an attack by substituting his or her prior input (i.e., replacing the real input with a different value that is to his or her advantage).
A need therefore exists for techniques for ensuring input consistency of the malicious players across multiple executions. A further need exists for techniques for ensuring input consistency that allow a party to prove he or she is using the same or related input (as agreed among the parties) to what was used in a prior execution.